package Leetcode.动态规划;

import java.util.List;

public class 斐波那契数列 {
    // 求第 n 个斐波那契数
    static int  fibonacci1(int n) {
        if (n == 0) return 0; // 返回 f(0)
        if (n == 1) return 1; // 返回 f(1)
        return fibonacci1(n - 1) + fibonacci1(n - 2); // 分解为两个子问题求解
    }

    //记忆法
    static int fibonacci2(int n, int[] dp) {

        if (n == 0) return 0;           // 返回 f(0)
        if (n == 1) return 1;           // 返回 f(1)
        if (dp[n] != 0) return dp[n];   // 若 f(n) 以前已经计算过，则直接返回记录的解
        dp[n] = fibonacci2(n - 1, dp) + fibonacci2(n - 2, dp); // 将 f(n) 则记录至 dp
        return dp[n];
    }

    // 求第 n 个斐波那契数
    static  int fibonacciMemorized(int n) {
        int[] dp = new int[n + 1]; // 用于保存 f(0) 至 f(n) 问题的解
        return fibonacci2(n, dp);
    }

    //动态规划
    // dp[1]=1 dp[n] = dp[n-1] + dp[n-2]

    static int fibonacci3(int n) {
        if (n == 0) return 0;
        int[] dp = new int[n+1];
        dp[1] = 1;
        for(int i=2; i<=n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }

    // 求第 n 个斐波那契数  优化减少空间消耗  o（1）
    static int fibonacci4(int n) {
        if (n == 0) return 0;           // 若求 f(0) 则直接返回 0
        int a = 0, b = 1;               // 初始化 f(0), f(1)
        for (int i = 2; i <= n; i++) {  // 状态转移求取 f(2), f(3), ..., f(n)
            int tmp = a;
            a = b;
            b = tmp + b;
        }
        return b;                       // 返回 f(n)
    }

    /**
     * 汉诺塔1.0
     * 采用递归的思路
     * 三要素如下：
     * 递归结束条件：只剩下最后一个盘子需要移动
     * 递归函数主功能：
     * 1.首先将 n-1 个盘子，从第一个柱子移动到第二个柱子
     * 2.然后将最后一个盘子移动到第三个柱子上
     * 3.最后将第二个柱子上的 n-1 个盘子，移动到第三个柱子上
     * 函数的等价关系式：
     * f(n,A,B,C) 表示将n个盘子从A移动到C
     * f(n,A,B,C)=f(n-1,A,C,B)+f(1,A,B,C)+f(n-1,B,A,C)
     *
     */
    public static void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
        movePlant(A.size(),A,B,C);
    }

    /**
     *
     * @param size 需要移动的盘子的数量
     * @param start 起始的柱子
     * @param auxiliary 辅助柱子
     * @param target 目标柱子
     */
    public static void movePlant(int size,List<Integer> start,List<Integer> auxiliary,List<Integer> target){
        //当只剩一个盘子时，直接将它从第一个柱子移动到第三个柱子
        if(size == 1){
            target.add(start.remove(start.size()-1));
            return;
        }
        //首先将 n-1 个盘子，从第一个柱子移动到第二个柱子
        movePlant(size - 1,start,target,auxiliary);
        //然后将最后一个盘子移动到第三个柱子上
        target.add(start.remove(start.size()-1));
        //最后将第二个柱子上的 n-1 个盘子，移动到第三个柱子上
        movePlant(size - 1,auxiliary,start,target);

    }
    /*
    #include <stdio.h>

// 函数原型声明
void moveDisk(char fromPeg, char toPeg, int disk);
void solveHanoi(int n, char fromPeg, char toPeg, char auxPeg);

int main() {
    int n; // 盘子的数量
    printf("请输入盘子的数量: ");
    scanf("%d", &n);
    solveHanoi(n, 'A', 'C', 'B'); // A, B, C 分别代表三根柱子
    return 0;
}

// 移动盘子的函数
void moveDisk(char fromPeg, char toPeg, int disk) {
    printf("移动盘子 %d 从柱子 %c 到柱子 %c\n", disk, fromPeg, toPeg);
}

// 解决汉诺塔问题的递归函数
void solveHanoi(int n, char fromPeg, char toPeg, char auxPeg) {
    if (n == 1) {
        // 只有一个盘子时，直接移动到目标柱子
        moveDisk(fromPeg, toPeg, 1);
    } else {
        // 将 n-1 个盘子从起始柱子移动到辅助柱子
        solveHanoi(n - 1, fromPeg, auxPeg, toPeg);
        // 移动最大的盘子到目标柱子
        moveDisk(fromPeg, toPeg, n);
        // 将 n-1 个盘子从辅助柱子移动到目标柱子
        solveHanoi(n - 1, auxPeg, toPeg, fromPeg);
    }
}

     */
/*
4柱
#include <stdio.h>

#define NUM_PEGS 4

void moveDisk(int fromPeg, int toPeg, int diskSize);
void moveTower(int height, int fromPeg, int toPeg, int auxPeg1, int auxPeg2);

int main() {
    int numDisks;
    printf("请输入盘子的数量: ");
    scanf("%d", &numDisks);
    moveTower(numDisks, 0, 3, 1, 2); // 从柱子0移动到柱子3，使用柱子1和柱子2作为辅助
    return 0;
}

void moveDisk(int fromPeg, int toPeg, int diskSize) {
    printf("移动盘子 %d 从柱子 %d 到柱子 %d\n", diskSize, fromPeg, toPeg);
}

void moveTower(int height, int fromPeg, int toPeg, int auxPeg1, int auxPeg2) {
    if (height >= 1) {
        // 递归移动上面height-1个盘子到辅助柱子auxPeg1
        moveTower(height - 1, fromPeg, auxPeg1, toPeg, auxPeg2);
        // 移动剩下的最大的盘子到目标柱子toPeg
        moveDisk(fromPeg, toPeg, height);
        // 递归移动之前移动到auxPeg1的height-1个盘子到目标柱子toPeg
        moveTower(height - 1, auxPeg1, toPeg, fromPeg, auxPeg2);
    }
}


 */

    public static void main(String[] args) {
        int n = 4;
        System.out.println(fibonacci1(n));
//        System.out.println(fibonacciMemorized(n));
//        System.out.println(fibonacci3(n));
//        System.out.println(fibonacci4(n));
    }

}
